//
//  Problem124.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 124. 二叉树中的最大路径和
 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 路径和 是路径中各节点值的总和。
 给你一个二叉树的根节点 root ，返回其 最大路径和 。

 示例 1：
     输入：root = [1,2,3]
     输出：6
     解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 示例 2：
     输入：root = [-10,9,20,null,null,15,7]
     输出：42
     解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 提示：
     树中节点数目范围是 [1, 3 * 104]
     -1000 <= Node.val <= 1000
 */
@objcMembers class Problem124: NSObject {
    func solution() {
        let root = TreeNode(-10)
        root.left = TreeNode(9)
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        
        print(maxPathSum(root))
    }
    
    /*
     思路：因为求的是路径，那么这条路径肯定有一个节点是这样的：
     这个节点的左右都在路径上 = sum(left) + node + sum(right)
     当然有特殊情况 这个节点的没有左节点 = node + sum(right), 或者没有右节点
     那么需要求出sum(left)的所有和中的最大值。现在题目变成提供一个节点。求出从根节点到叶子结点的路径的和的最大值。
     
     我们可以使用穷举法的方式：求出每个节点这样形式的和，找到最大值接口
     那么我是试试root节点是否是这样的情况，然后需要求left和right节点的最大和
     */
    
    var lastMaxValue = Int.min
    func maxPathSum(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        } else if root?.left == nil, root?.right == nil {
            return root!.val
        }
        
        let sumLeft  = getDepthSum(root?.left)
        let sumRight = getDepthSum(root?.right)
        
        lastMaxValue = max(lastMaxValue, root!.val + sumLeft + sumRight)
        
        return root!.val
    }
    
    // 求根节点到叶子结点最大的路径和
    func getDepthSum(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        } else if root?.left == nil, root?.right == nil {
            return root!.val
        }
        
        let leftSum = getDepthSum(root?.left)
        let rightSum = getDepthSum(root?.right)
        
        return max(leftSum, rightSum) + root!.val
    }
}
